package com.cuz.daileetcode;

import com.sun.corba.se.pept.transport.InboundConnectionCache;
import com.sun.media.sound.RIFFInvalidDataException;

import java.util.Arrays;

/**
 * @author cuzz
 * @version 1.0
 * @description: 34. 在排序数组中查找元素的第一个和最后一个位置
 * 给定一个按照升序排列的整数数组 nums，
 * 和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 * 进阶：
 * 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
 * 示例 1：
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 * 示例 2：
 * 输入：nums = [5,7,7,8,8,10], target = 6
 * 输出：[-1,-1]
 * 示例 3：
 * 输入：nums = [], target = 0
 * 输出：[-1,-1]
 * @date 11:17 2021/10/7
 **/
public class Day19 {

    static class S1 {
        public static void main(String[] args) {
//            System.out.println(3 / 2);
//            System.out.println(findFirst(new int[]{1, 2, 2, 3, 3, 4, 5, 6}, 2));
//            System.out.println(findLast(new int[]{1, 2, 2, 3, 3, 4, 5, 6}, 2));

            int[] nums = {1};
            System.out.println(findLast(nums, 1));

            System.out.println(Arrays.toString(searchRange(nums, 1)));
        }

        public static int[] searchRange(int[] nums, int target) {
            if (nums==null||nums.length==0){
                return new int[]{-1,-1};
            }
            return new int[]{findFirst(nums, target), findLast(nums, target)};
        }


        public static int findLast(int[] nums, int target) {
            //1, 2, 2, 3, 3, 4, 5, 6 6
            int low = 0;
            int high = nums.length - 1;
            int res = -1;
            while (low < high) {
                // l=0 h=8 mid=4
                // h=3 l =0 mid=1
                int mid = (high + low + 1) / 2;
                if (nums[mid] == target) {
                    res = mid;
                    low = mid;
                } else if (nums[mid] > target) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            if (res == -1 && nums[high] == target) {
                res=high;
            }
            return res;
        }

        public static int findFirst(int[] nums, int target) {
            int low = 0;
            int high = nums.length - 1;
            int res = -1;
            while (low < high) {
                int mid = ((high - low) / 2) + low;
                if (nums[mid] == target) {
                    high = mid;
                    res = mid;
                } else if (nums[mid] < target) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            if (res == -1 && nums[low] == target) {
                res=low;
            }
            return res;
        }
    }
}
